#define TEST

#ifndef DS
#include "ds.cpp"
#endif

#include <iostream>
#include <vector>
#include <ctime>
using namespace std;

// 生成随机整形数组
vector<int> GenerateRandIntArr(int len, int minVal = 0, int maxVal = RAND_MAX)
{
    srand((unsigned int)time(NULL));

    if (minVal > maxVal)
        return vector<int>();

    vector<int> res(len);
    for (int i = 0; i < len; ++i)
        res[i] =  rand() % (maxVal - minVal + 1) + minVal;

    return res;
}

// 生成随机字符串
string GenerateRandString(int len)
{
    srand((unsigned int)time(NULL));

    string str(len, 0);
    int type = 0;   // 小写字母 大写字母 数字
    for (int i = 0; i < len; ++i)
    {
        type = rand() % 3;
        switch (type)
        {
        case 0 : // 小写
            str[i] = 'a' + rand() % 26;
            break;
        case 1: // 大写
            str[i] = 'A' + rand() % 26;
            break;
        case 2: // 数字
            str[i] = '0' + rand() % 10;
            break;
        }
    }

    return str;
}

// 生成随机链表
ListNode* GenerateLinkedList(int len, int minVal = 0, int maxVal = RAND_MAX)
{
    srand((unsigned int)time(NULL));

    ListNode dummyHead;
    while (len > 0)
    {
        ListNode* node = new ListNode(rand() % (maxVal - minVal + 1));
        node->next = dummyHead.next;
        dummyHead.next = node;
        --len;
    }

    return dummyHead.next;
}

// 打印数组
template <typename _Type>
ostream& operator<<(ostream& cout, const vector<_Type>& v)
{
    for (const auto& elem : v)
        cout << elem << ' ';
    return cout;
}

// 打印链表
ostream& operator<<(ostream& cout, ListNode* p)
{
    if (p == nullptr)
        return cout;
    while (p->next != nullptr)
    {
        cout << p->val << "->";
        p = p->next;
    }
    cout << p->val;
    return cout;
}

// 分层打印二叉树
ostream& operator<<(ostream& cout, TreeNode* root)
{
    if (root == nullptr)
        return cout;
    queue<TreeNode*> q;
    q.push(root);
    int toBeVisit = 1, nextLevelCount = 0;
    TreeNode* cur;
    while (!q.empty())
    {
        cur = q.front();
        q.pop();
        --toBeVisit;
        cout << cur->val << ' ';

        if (cur->left)
        {
            q.push(cur->left);
            ++nextLevelCount;
        }
        if (cur->right)
        {
            q.push(cur->right);
            ++nextLevelCount;
        }

        if (toBeVisit == 0)
        {
            toBeVisit = nextLevelCount;
            nextLevelCount = 0;
            cout << endl;
        }
    }

    return cout;
}